package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/*
https://leetcode.cn/problems/path-sum-ii/description/
https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

113. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。

例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
*/
class leetcode_113 {
    @Test
    fun test_1() {
        val root = TreeNode(5)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n4 = TreeNode(4)
        val n4_v2 = TreeNode(4)
        val n5 = TreeNode(5)
        val n7 = TreeNode(7)
        val n8 = TreeNode(8)
        val n11 = TreeNode(11)
        val n13 = TreeNode(13)
        root.left = n4
        root.right = n8

        n4.left = n11

        n11.left = n7
        n11.right = n2

        n8.left = n13
        n8.right = n4_v2

        n4_v2.left = n5
        n4_v2.right = n1
        val actual = pathSum(root, 22)
        val expect = arrayListOf(arrayListOf(5, 4, 11, 2), arrayListOf(5, 8, 4, 5))
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_2() {
        val root = TreeNode(1)
        root.left = TreeNode(2)
        root.right = TreeNode(3)

        val actual = pathSum(root, 5)

        val expect = ArrayList<ArrayList<Int>>()
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_3() {
        val actual = pathSum(null, 0)
        val expect = ArrayList<ArrayList<Int>>()
        Assert.assertEquals(actual, expect)
    }

    private fun pathSum(root: TreeNode?, targetSum: Int): List<List<Int>> {
        val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        if (null == root) {
            return result
        }
        val path: ArrayList<Int> = arrayListOf<Int>(root.`val`)
        // // TODO : 注意这里的参数path要传递root value
        pathSum1(root, root.`val`, targetSum, path, result)
        return result
//        return pathSum2(root, targetSum)
    }

    private fun pathSum1(root: TreeNode?, sum: Int, targetSum: Int, path: ArrayList<Int>, result: ArrayList<ArrayList<Int>>) {
        // 深度遍历 - 前序遍历 中 左 右 - 递归
        // T - N
        // S - N
        // 1 确认函数参数以及返回值
        // 2 确认终止条件
        // 终止条件
        if (root == null) {
            return
        }

        // 3 确认单次递归的处理逻辑：前序遍历
        // 中
        // 收集条件： 左空，right null, sum == target
        if (root.left == null && root.right == null) {
            // 找到一条路径
            if (sum == targetSum) {
                // TODO : 注意这里要copy path 数据，否则得不到想要的数据
                val list: ArrayList<Int> = ArrayList<Int>()
                list.addAll(path)
                result.add(list)
            }
            return
        }

        var n: Int = sum
        // 左
        root.left?.let {
            println("root.left=${it.`val`}")
            n = n + it.`val`
            path.add(it.`val`)
            pathSum1(it, n, targetSum, path, result)
            // 回溯
            n = n - it.`val`
            path.removeAt(path.size - 1)
        }


        // 右
        root.right?.let {
            n = n + it.`val`
            path.add(it.`val`)
            pathSum1(it, n, targetSum, path, result)
            n = n - it.`val` // 回溯
            path.removeAt(path.size - 1)
        }
    }

    private fun pathSum2(root: TreeNode?, targetSum: Int): List<List<Int>> {
        // 深度遍历 - 前序遍历 中左右 - 统一迭代法
        // T - N
        // S - N

        // 栈 - 右左中
        // path 转成 list

        val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        if (null == root) {
            return result
        }

        val stack: LinkedList<Triple<TreeNode, Boolean, Info>> = LinkedList<Triple<TreeNode, Boolean, Info>>()
        stack.push(Triple<TreeNode, Boolean, Info>(root, false, Info(root.`val`, "" + root.`val`)))

        while (!stack.isEmpty()) {
            val triple: Triple<TreeNode, Boolean, Info> = stack.pop()
            val node = triple.first
            val visited = triple.second
            val info: Info = triple.third

            if (visited) {
                // 判断找到了path，path 转成 list
                if (node.left == null && node.right == null && info.sum == targetSum) {
                    // TODO: val items :ArrayList<String> = info.path.splitBy(",")
                    val items: List<String> = info.path.split(",")
                    val r: ArrayList<Int> = ArrayList<Int>()
                    for (str in items) {
                        r.add(str.toInt())
                    }
                    result.add(r)
                }
                continue
            }
            // 右
            node.right?.let {
                stack.push(Triple<TreeNode, Boolean, Info>(it, false, Info(info.sum + it.`val`, info.path + "," + it.`val`)))
            }
            // 左

            node.left?.let {
                stack.push(Triple<TreeNode, Boolean, Info>(it, false, Info(info.sum + it.`val`, info.path + "," + it.`val`)))
            }
            // 中
            stack.push(Triple<TreeNode, Boolean, Info>(node, true, info))
        }
        return result
    }

    private data class Info(val sum: Int, val path: String)
}